﻿// 705 网格.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>



using namespace std;
/*
http://oj.daimayuan.top/course/5/problem/253

有一个 n×m的网格，现在我们想用 1×2
 的矩形铺满它，要求矩形只能横着铺或者竖着铺、矩形不能超出网格的边界并且不同的矩形之间不能相互覆盖。

请问有多少种不同的铺法？请输出铺法数对 109+7取模的结果。

输入格式
一行两个整数 n,m表示网格的大小。

输出格式
一行一个整数表示答案。

样例输入
2 2
样例输出
2
数据范围
对于 100% 的数据，保证 2≤n,m≤18。
*/



const int N = 19;
int dp[2][1 << N];
int n, m;
const int M = 1000000007;

void solve() {
    int* crt = dp[0]; int* next = dp[1];
    crt[0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            for (int used = 0; used < 1 << m; used++) {
                if ((used >> j & 1)) {
                    next[used] = crt[used & ~(1 << j)];
                }
                else {
                    int res = 0;
                    if (j + 1 < m && !(used >> (j + 1) & 1)) {
                        res += crt[used | 1 << (j + 1)];
                    }
                    if (i + 1 < n) {
                        res += crt[used | 1 << j];
                    }
                    next[used] = res % M;
                }
            }
            swap(crt, next);
        }
    }
    printf("%d\n", crt[0]);
}


int main()
{
    cin >> n >> m;
    solve();

    return 0;
}

